package _interview100;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 42. 接雨水
 */
public class No42 {
    /**
     * 1. 双指针
     */
    public int trap1(int[] height) {
        int n = height.length;
        int left = 0, right = n - 1, answer = 0;
        int curMaxLeft = height[left], curMaxRight = height[right];
        while (left < right) {
            if (height[left] < height[right]) {
                answer += (curMaxLeft - height[left]);
                left++;
                curMaxLeft = Math.max(curMaxLeft, height[left]);
            } else {
                answer += (curMaxRight - height[right]);
                right--;
                curMaxRight = Math.max(curMaxRight, height[right]);
            }
        }
        return answer;
    }

    /**
     * 2. 单调栈
     */
    public int trap2(int[] height) {
        int ans = 0;

        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                Integer pop = stack.pop();
                if (stack.isEmpty()) break;
                int w = i - stack.peek() - 1;
                int h = Math.min(height[stack.peek()], height[i]) - height[pop];
                ans += w * h;
            }
            stack.push(i);
        }
        return ans;
    }
}
